package 动态规划.背包问题;

import java.util.Scanner;

public class _01背包问题优化版 {

	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		int m=sc.nextInt();
		int n=sc.nextInt();
		int[] dp=new int[m+1];
		int[] w=new int[n+1];
		int[] c=new int[n+1];
		for(int i=1;i<=n;i++) {
			w[i]=sc.nextInt();
			c[i]=sc.nextInt();
		}
		for(int x=1;x<=n;x++) 
			/*dp表前面的数据关联到后面的数据，所以要先循环后面的变量*/
			for(int y=m;y>=1;y--) {
				if(y>=w[x]) 
					dp[y]=max(dp[y],dp[y-w[x]]+c[x]);
			}
		System.out.println(dp[m]);
	}
	private static int max(int i, int j) {
		return i>j?i:j;
	}
}
